package com.cango.student.algorithm.skiplist;

import java.util.Random;

/**
 * 跳表的一种实现方法。
 * 跳表中存储的是正整数，并且存储的是不重复的。
 * <p>
 * Author：ZHENG
 */
public class skiplist {

    private static final int MAX_LEVEL = 16;

    private int levelCount = 1;

    // 带头链表
    private Node head = new Node();

    private Random r = new Random();

    /**
     * 查找
     * @param value
     * @return
     */
    public Node find(int value) {
        Node p = head;
        // 从最高层
        for (int i = levelCount - 1; i >= 0; --i) {
            while (p.forwords[i] != null && p.forwords[i].data < value) {
                p = p.forwords[i];
            }
        }

        // 第0层
        if (p.forwords[0] != null && p.forwords[0].data == value) {
            return p.forwords[0];
        } else {
            return null;
        }
    }

    /**
     * 插入
     * @param value
     */
    public void insert(int value) {
        // 需要插入的层数
        int level = randomLevel();
        Node newNode = new Node();
        newNode.data = value;
        newNode.maxLevel = level;
        // 新增数组，大小为层数
        Node update[] = new Node[level];
        for (int i = 0; i < level; ++i) {
            update[i] = head;
        }

        Node p = head;
        // 自上而下，找到每一层的关键节点
        for (int i = level - 1; i >= 0; --i) {
            // 指针不断的向前
            while (p.forwords[i] != null && p.forwords[i].data < value) {
                p = p.forwords[i];
            }
            update[i] = p;
        }

        for (int i = 0; i < level; ++i) {
            // 将newNode插入在update后
            newNode.forwords[i] = update[i].forwords[i];
            update[i].forwords[i] = newNode;
        }

        // 更新levelCount
        if (levelCount < level) levelCount = level;
    }

    /**
     * 删除
     * @param value
     */
    public void delete(int value) {
        Node[] update = new Node[levelCount];
        Node p = head;
        // 自上而下，寻找节点，并保存
        for (int i = levelCount - 1; i >= 0; --i) {
            while (p.forwords[i] != null && p.forwords[i].data < value) {
                p = p.forwords[i];
            }
            update[i] = p;
        }

        // 最底层是否相等
        if (p.forwords[0] != null && p.forwords[0].data == value) {
            // 循环取得上一层的node
            for (int i = levelCount - 1; i >= 0; --i) {
                if (update[i].forwords[i] != null && update[i].forwords[i].data == value) {
                    update[i].forwords[i] = update[i].forwords[i].forwords[i];
                }
            }
        }
    }


    /**
     * 生成随机索引层
     * @return
     */
    private int randomLevel() {
        int level = 1;
        for (int i = 1; i < MAX_LEVEL; ++i) {
            // 基数就加一
            if (r.nextInt() % 2 == 1) {
                level++;
            }
        }

        return level;
    }

    /**
     * 打印所有
     */
    public void printAll() {
        Node p = head;
        while (p.forwords[0] != null) {
            System.out.print(p.forwords[0] + " ");
            p = p.forwords[0];
        }
        System.out.println();
    }

    public class Node {
        private int data = -1;
        // 按层前
        private Node forwords[] = new Node[MAX_LEVEL];
        // 最大层数
        private int maxLevel = 0;

        @Override
        public String toString() {
            StringBuilder builder = new StringBuilder();
            builder.append("{ data: ");
            builder.append(data);
            builder.append("; levels: ");
            builder.append(maxLevel);
            builder.append(" }");

            return builder.toString();
        }
    }

}